package org.example.datastructure.ch13;

import org.example.datastructure.ch12.DisJointSet;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class adjListGraph {
    verNode[] verList;
    int Vers;
    int Edges;
    public adjListGraph(int vSize,int[] d){
        Vers = vSize;
        Edges = 0;
        verList = new verNode[vSize];
        for(int i=0;i<vSize;i++){
            verList[i].val = d[i];
        }
    }

    void insert(int x,int y,int w){
        int u = find(x);
        int v = find(y);
        verList[u].head = new edgeNode(v,w,verList[u].head);
        ++Edges;
    }

    boolean exist(int x,int y){
        int u = find(x);
        int v = find(y);
        edgeNode p = verList[u].head;
        while(p!=null&&p.end!=v){
            p = p.next;
        }
        if(p==null) return false;
        return true;
    }

    void dfs(){
        boolean[] visited = new boolean[Vers];
        for(int i=0;i<Vers;i++){
            if(!visited[i]){
                dfs(i,visited);
            }
        }
    }

    void dfs(int start,boolean[] visited){
        edgeNode p = verList[start].head;
        visited[start] = true;
        while(p!=null){
            if(!visited[p.end]) dfs(p.end,visited);
            p = p.next;
        }
    }

    void bfs(){
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[Vers];
        int currentNode;
        edgeNode p;
        for(int i=0;i<Vers;i++){
            if(visited[i]) continue;
            q.offer(i);
            while(!q.isEmpty()){
                currentNode = q.poll();
                if(visited[currentNode]) continue;
                visited[currentNode] = true;
                p = verList[currentNode].head;
                while(p!=null){
                    if(!visited[p.end]) q.offer(p.end);
                    p = p.next;
                }
            }
        }
    }

    int find(int v){
        for(int i=0;i<Vers;i++){
            if(verList[i].val==v){
                return i;
            }
        }
        return -1;
    }

    void topSort(){
        int[] inDegree = new int[Vers];
        Queue<Integer> q = new LinkedList<>();
        edgeNode p;
        int current;
        for(int i=0;i<Vers;i++){
            for(p=verList[i].head;p!=null;p=p.next){
                inDegree[p.end]++;
            }
        }
        for(int i=0;i<Vers;i++){
            if(inDegree[i]==0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            current = q.poll();
            System.out.print(current+" ");
            for(p=verList[current].head;p!=null;p=p.next){
                if(--inDegree[p.end]==0){
                    q.offer(p.end);
                }
            }
        }
        System.out.println();
    }

    void criticalPath(){
        int[] ee = new int[Vers],le = new int[Vers];
        int[] top = new int[Vers],inDegree = new int[Vers];
        Queue<Integer> q = new LinkedList<>();
        int i=0;
        edgeNode p;
        for(int j=0; j<Vers;j++){
            for(p=verList[j].head;p!=null;p=p.next){
                inDegree[p.end]++;
            }
        }
        for(int j=0;i<Vers;j++){
            if(inDegree[j]==0) q.offer(j);
        }
        while(!q.isEmpty()){
            top[i] = q.poll();
            for(p=verList[top[i]].head;p!=null;p=p.next){
                if(--inDegree[p.end]==0) q.offer(p.end);
            }
            ++i;
        }
        for(i=0;i<Vers;i++){
            for(p=verList[top[i]].head;p!=null;p=p.next){
                if(ee[p.end]<ee[top[i]]+p.weight){
                    ee[p.end] = ee[top[i]]+p.weight;
                }
            }
        }
        for(i=Vers-1;i>=0;i--){
            le[i] = ee[top[Vers-1]];
        }
        for(i=Vers-1;i>=0;i--){
            for(p=verList[top[i]].head;p!=null;p=p.next){
                if(le[p.end]-p.weight<le[top[i]]){
                    le[top[i]] = le[p.end]-p.weight;
                }
            }
        }
        for(i=0;i<Vers;i++){
            if(le[top[i]]==ee[top[i]]){
                System.out.println(top[i]+" "+le[top[i]]);
            }
        }

    }
    void kruskal(){
        int count = 0;
        int u,v;
        PriorityQueue<edge> pq = new PriorityQueue<>();
        DisJointSet ds = new DisJointSet(Vers);
        edge e;
        edgeNode p;
        for(int i=0;i<Vers;i++){
            for(p=verList[i].head;p!=null;p=p.next){
                if(i<p.end){
                    e = new edge(i,p.end,p.weight);
                    pq.offer(e);
                }
            }
        }
        while(count<Vers-1){
            e = pq.poll();
            u = ds.find(e.begin);
            v = ds.find(e.end);
            if(u!=v){
                count++;
                ds.union(u,v);
                System.out.println(verList[e.begin].val+" "+verList[e.end].val+" "+e.weight);
            }
        }

    }
    void prim(){
        boolean[] flag = new boolean[Vers];
        int[] lowerCost = new int[Vers];
        int[] startNode = new int[Vers];
        edgeNode p;
        int min;
        int start,i,j;
        for(i=0;i<Vers;i++){
            flag[i] = false;
            lowerCost[i] = Integer.MAX_VALUE;
        }
        start = 0;
        for(i=1;i<Vers;i++){
            for(p=verList[start].head;p!=null;p=p.next){
                if(!flag[p.end]&&p.weight<lowerCost[p.end]){
                    lowerCost[p.end] = p.weight;
                    startNode[p.end] = start;
                }
            }
            flag[start] = true;
            min = Integer.MAX_VALUE;
            for(j=0;j<Vers;j++){
                if(lowerCost[j]<min){
                    min = lowerCost[j];
                    start = j;
                }
            }
            System.out.println(verList[startNode[start]].val+" "+verList[start].val+" "+min);
            lowerCost[start] = Integer.MAX_VALUE;
        }
    }
    void unWeightShortDistance(int sNo){
        Queue<Integer> q = new LinkedList<>();
        int[] distance = new int[Vers];
        int[] prev = new int[Vers];
        int u;
        edgeNode p;
        for(int i=0;i<Vers;i++){
            distance[i] = Integer.MAX_VALUE;
        }
        distance[sNo]=0;
        prev[sNo] = sNo;
        q.offer(sNo);
        while(!q.isEmpty()){
            u = q.poll();
            for(p=verList[u].head;p!=null;p=p.next){
                if(distance[p.end]>distance[u]+1){
                    distance[p.end] = distance[u]+1;
                    prev[p.end] = u;
                    q.offer(p.end);
                }
            }
        }
        for(int i=0;i<Vers;i++){
            printPath(sNo,i,prev);
        }
    }
    void printPath(int start,int end,int[] prev){
        if(start==end){
            System.out.println(verList[start].val);
            return;
        }
        printPath(start,prev[end],prev);
        System.out.println(verList[end].val);
    }
    void Dijkstra(int start,int sNo){
        int[] distance = new int[Vers];
        int[] prev = new int[Vers];
        boolean[] known = new boolean[Vers];
        int u=0,i,j;
        edgeNode p;
        int min;
        for(i=0;i<Vers;i++){
            known[i] = false;
            distance[i] = Integer.MAX_VALUE;
        }
        distance[sNo] = 0;
        prev[sNo] = sNo;
        for(i=1;i<Vers;i++){
            min = Integer.MAX_VALUE;
            for(j=0;j<Vers;j++){
                if(!known[j]&&distance[j]<min){
                    min = distance[j];
                    u = j;
                }
                known[u] = true;
            }
            for(p=verList[u].head;p!=null;p=p.next){
                if(!known[p.end]&&distance[p.end]>min+ p.weight){
                    distance[p.end] = min+p.weight;
                    prev[p.end] = u;
                }
            }
        }
        for (i=0;i<Vers;i++){
            printPath(sNo,i,prev);
        }
    }
    void Floyd(int[][] edge){
        int[][] d = new int[Vers][Vers];
        int[][] prev = new int[Vers][Vers];
        int i,j,k;
        for(i=0;i<Vers;i++){
            for(j=0;j<Vers;j++){
                d[i][j] = edge[i][j];
                prev[i][j] = (edge[i][j]!=Integer.MAX_VALUE)?i:-1;
            }
            for(k=0;k<Vers;k++){
                for(i=0;i<Vers;i++){
                    for(j=0;j<Vers;j++){
                        if(d[i][k]+d[k][j]<d[i][j]){
                            d[i][j] = d[i][k]+d[k][j];
                            prev[i][j] = prev[k][j];
                        }
                    }
                }
            }
        }
    }
}
class edgeNode{
    int end;
    int weight;
    edgeNode next;
    public edgeNode(int end, int weight){
        this.end = end;
        this.weight = weight;
        this.next = null;
    }
    public edgeNode(int end, int weight, edgeNode next){
        this.end = end;
        this.weight = weight;
        this.next = next;
    }
}
class verNode{
    int val;
    edgeNode head;
    public verNode(){
        this.val = 0;
        this.head = null;
    }
    public verNode(int val){
        this.val = val;
        this.head = null;
    }
    public verNode(edgeNode h){
        this.head = h;
    }

}
class edge {
    int begin;
    int end;
    int weight;

    public edge(int begin, int end, int weight) {
        this.begin = begin;
        this.end = end;
        this.weight = weight;
    }
}
